package code20210926;

public class C1137 {

	public static void main(String[] args) {
		/*
		StringBuilder sb = new StringBuilder();
		sb.append("{");
		for(int i=0;i<=37;i++) {
			String s = i==37?new C1137().tribonacci(i)+"":new C1137().tribonacci(i)+",";
			sb.append(s);
		}
		sb.append("}");
		System.out.println(sb.toString());*/
		int[] arr = {0,1,1,2,4,7,13,24,44,81,149,274,504,927,1705,3136,5768,10609,19513,35890,66012,121415,223317,410744,755476,1389537,2555757,4700770,8646064,15902591,29249425,53798080,98950096,181997601,334745777,615693474,1132436852,2082876103};
		System.out.println(arr[25]);
	}
	public int tribonacci(int n) {
		int[] dp = new int[n+1];
		dp[0] = 0;
		if(n>0) dp[1] = 1;
		if(n>1) dp[2] = 1;
		for(int i=3;i<dp.length;i++) {
			dp[i] = dp[i-1]+dp[i-2]+dp[i-3];
		}
		return dp[n];
    }

}
